package com.example.sprintbootarithmetic.sort.ShellSort;

import java.util.Arrays;

/**
 * ����
 *
 * @description:希尔排序
 * @author: daixingyu
 * @date: 2021-06-27  10:59
 */
public class ShellSort {
    public static void shellsort(int[] array) {
        int demo = 0;
        for (int gap = array.length / 2; gap > 0; gap /= 2) {//对应的外层循环次数为分组的大小
            for (int j = gap; j < array.length; j++) {
                for (int h = j - gap; h >= 0; h -= gap) {//h-gap
                    if (array[h] > array[h + gap]) {
                        demo = array[h];
                        array[h] = array[h + gap];
                        array[h + gap] = demo;
                    }
                }
            }
        }
    }

    /**
     * ��������
     *
     * @param array
     * @description:ϣ��������λ��
     * @return: void
     * @author: daixingyu
     * @date: 2021-06-27  10:59
     */
    public static void shellsort2(int[] array) {
        int demo = 0;
        for (int gap = array.length / 2; gap > 0; gap /= 2) {
            for (int j = gap; j < array.length; j++) {
                int h = j;
                demo = array[h];
                if (array[h] < array[h - gap]) {
                    while (h - gap >= 0 && demo < array[h - gap]) {
                        array[h] = array[h - gap];
                        h -= gap;
                    }
                    array[h] = demo;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] array = new int[]{2, 52, 32, 42, 1251, 0};
        shellsort(array);
        System.out.println(Arrays.toString(array));
    }
}
